{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of Good Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countGood"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计好子数组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>&nbsp;和一个整数 <code>k</code>&nbsp;，请你返回 <code>nums</code>&nbsp;中 <strong>好</strong>&nbsp;子数组的数目。</p>\n",
    "\n",
    "<p>一个子数组 <code>arr</code>&nbsp;如果有 <strong>至少</strong>&nbsp;<code>k</code>&nbsp;对下标 <code>(i, j)</code>&nbsp;满足 <code>i &lt; j</code>&nbsp;且 <code>arr[i] == arr[j]</code>&nbsp;，那么称它是一个 <strong>好</strong>&nbsp;子数组。</p>\n",
    "\n",
    "<p><strong>子数组</strong>&nbsp;是原数组中一段连续 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,1,1,1,1], k = 10\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>唯一的好子数组是这个数组本身。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,1,4,3,2,2,4], k = 2\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>总共有 4 个不同的好子数组：\n",
    "- [3,1,4,3,2,2] 有 2 对。\n",
    "- [3,1,4,3,2,2,4] 有 3 对。\n",
    "- [1,4,3,2,2,4] 有 2 对。\n",
    "- [4,3,2,2,4] 有 2 对。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-good-subarrays](https://leetcode.cn/problems/count-the-number-of-good-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-good-subarrays](https://leetcode.cn/problems/count-the-number-of-good-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,1,1]\\n10', '[3,1,4,3,2,2,4]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        fast, slow = -1, 0\n",
    "        n = len(nums)\n",
    "        hashmap = {}\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for fast in range(n):\n",
    "            if hashmap.get(nums[fast], -1) == -1:\n",
    "                hashmap[nums[fast]] = 1\n",
    "            else:\n",
    "                cnt += hashmap[nums[fast]]\n",
    "                hashmap[nums[fast]] += 1\n",
    "            while cnt>=k:\n",
    "                ans += (n-fast)\n",
    "                if hashmap[nums[slow]]>1:\n",
    "                    cnt -= (hashmap[nums[slow]]-1)\n",
    "                hashmap[nums[slow]] -= 1\n",
    "                slow += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=res=left=0\n",
    "        temp=Counter()\n",
    "        \n",
    "        for right in range(n):\n",
    "            res+=temp[nums[right]]\n",
    "            temp[nums[right]]+=1\n",
    "            ans+=left\n",
    "            while res>=k:\n",
    "                ans+=1\n",
    "                temp[nums[left]]-=1\n",
    "                res-=temp[nums[left]]\n",
    "                left+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        fast, slow = -1, 0\n",
    "        n = len(nums)\n",
    "        hashmap = {}\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        while fast<n:\n",
    "            if cnt>=k:\n",
    "                ans += (n-fast)\n",
    "                #print(\"fast:\" , fast)\n",
    "                if hashmap[nums[slow]]>1:\n",
    "                    cnt -= (hashmap[nums[slow]]-1)\n",
    "                hashmap[nums[slow]] -= 1\n",
    "                slow += 1\n",
    "            else:\n",
    "                fast += 1\n",
    "                if fast>=n:\n",
    "                    break\n",
    "                if hashmap.get(nums[fast], -1) == -1:\n",
    "                    hashmap[nums[fast]] = 1\n",
    "                else:\n",
    "                    cnt += hashmap[nums[fast]]\n",
    "                    hashmap[nums[fast]] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter()\n",
    "        n = len(nums)\n",
    "        res = l = r = pairs = 0\n",
    "        while r < n:\n",
    "            while r < n and pairs < k:\n",
    "                pairs += c[nums[r]]\n",
    "                c[nums[r]] += 1\n",
    "                r += 1 \n",
    "                res += l\n",
    "            while pairs >= k:\n",
    "                c[nums[l]] -= 1\n",
    "                pairs -= c[nums[l]]\n",
    "                l += 1\n",
    "                res += 1 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        counter = Counter()\n",
    "        cnt = ret = 0\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            cnt += counter[x]\n",
    "            counter[x] += 1\n",
    "            if cnt >= k:\n",
    "                while True:\n",
    "                    y = nums[left]\n",
    "                    if counter[y] <= 1:\n",
    "                        left += 1\n",
    "                        counter[y] -= 1\n",
    "                    else:\n",
    "                        if cnt - counter[y] + 1 >= k:\n",
    "                            left += 1\n",
    "                            cnt -= counter[y] - 1\n",
    "                            counter[y] -= 1\n",
    "                        else:\n",
    "                            ret += left + 1\n",
    "                            break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        pairNum = left = ans = 0\n",
    "        for n in nums:\n",
    "            pairNum += cnt[n]\n",
    "            cnt[n] += 1\n",
    "\n",
    "            while 1:\n",
    "                m = nums[left]\n",
    "                if pairNum - cnt[m] + 1 < k: break\n",
    "                cnt[m] -= 1\n",
    "                pairNum -= cnt[m]\n",
    "                left += 1\n",
    "            \n",
    "            if pairNum >= k:\n",
    "                ans += left + 1\n",
    "            \n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        # 1. 哈希表统计敞口内每个元素的出现次数\n",
    "        # cnt = Counter()\n",
    "        # ans = left = pairs = 0\n",
    "        # for x in nums:\n",
    "        #     pairs += cnt[x]\n",
    "        #     cnt[x] += 1 # 移入右端点\n",
    "        #     while pairs - cnt[nums[left]] + 1 >= k:\n",
    "        #         cnt[nums[left]] -= 1 # 移出左端点\n",
    "        #         pairs -= cnt[nums[left]]\n",
    "        #         left += 1\n",
    "        #     if pairs >= k:\n",
    "        #         ans += left + 1\n",
    "        # return ans\n",
    "\n",
    "        # 2. 把更新ans的逻辑写在循环内内部\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1 \n",
    "            ans += left\n",
    "            while pairs >= k:\n",
    "                ans += 1\n",
    "                cnt[nums[left]] -= 1 \n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1  # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        numDict = {}\n",
    "        currentpairCnt = 0\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        while j < len(nums):\n",
    "            if numDict.get(nums[j]) is None:\n",
    "                numDict[nums[j]] = 0\n",
    "            currentpairCnt += numDict[nums[j]]\n",
    "            numDict[nums[j]] += 1\n",
    "            j += 1\n",
    "            if currentpairCnt < k:\n",
    "                continue\n",
    "            while currentpairCnt-numDict[nums[i]]+1 >= k:\n",
    "                currentpairCnt -= numDict[nums[i]]-1\n",
    "                numDict[nums[i]] -= 1\n",
    "                i += 1\n",
    "            res += i+1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if cnt >= k:\n",
    "                # print(i, j, cnt, k, n - j + 1)\n",
    "                ans += n - j + 1\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] > 0:\n",
    "                    cnt -= d[nums[i]]\n",
    "                continue\n",
    "            while j < n:\n",
    "                d[nums[j]] += 1\n",
    "                if d[nums[j]] > 1:\n",
    "                    cnt += d[nums[j]] - 1\n",
    "                if cnt >= k:\n",
    "                    # print(i, j, cnt)\n",
    "                    ans += n - j\n",
    "                    j += 1\n",
    "                    break\n",
    "                j += 1\n",
    "            # print(d)\n",
    "            d[nums[i]] -= 1\n",
    "            # print(d)\n",
    "            # print(d[nums[i]])\n",
    "            if d[nums[i]] > 0:\n",
    "                cnt -= d[nums[i]]\n",
    "                # print(cnt)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        res = l = 0\n",
    "        cnt = Counter()\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            t += cnt[nums[i]]\n",
    "            cnt[nums[i]] += 1\n",
    "\n",
    "            while t >= k:\n",
    "                res += n - i\n",
    "                t -= cnt[nums[l]] - 1\n",
    "                cnt[nums[l]] -= 1\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1  # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        l = pairs = ans = 0\n",
    "        cnt = Counter()\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while pairs - (cnt[nums[l]] - 1) >= k:\n",
    "                pairs -= cnt[nums[l]] - 1\n",
    "                cnt[nums[l]] -= 1\n",
    "                l += 1\n",
    "            if pairs >= k:\n",
    "                ans += l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        my_dict=collections.defaultdict(int)\n",
    "        my_dict[nums[0]]+=1\n",
    "        result=0\n",
    "        index1=0\n",
    "        index2=1\n",
    "        sum1=0\n",
    "        while index2<len(nums):\n",
    "            v1=nums[index2]\n",
    "            my_dict[v1]+=1\n",
    "            count1=my_dict[v1]-1\n",
    "            if sum1+count1>=k:\n",
    "                my_dict[v1]-=1\n",
    "                result+=len(nums)-index2\n",
    "                v2=nums[index1]\n",
    "                num_before=my_dict[v2]\n",
    "                sum1-=(num_before-1)\n",
    "                index1+=1\n",
    "                my_dict[v2]-=1\n",
    "            else:\n",
    "                index2+=1\n",
    "                sum1+=count1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums, k):\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        c = 0\n",
    "        left = 0\n",
    "        for x in nums:\n",
    "            c += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while c >= k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                c -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            # 子数组越长越符合要求\n",
    "            # < left\n",
    "            ans += left\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def choose(a: int) -> int:\n",
    "    return a*(a-1)//2 if a else 0\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        left, right = len(nums), len(nums) - 1\n",
    "        sum_k = ans = 0\n",
    "        hashtable = dict()\n",
    "        while True:\n",
    "            while sum_k < k:\n",
    "                if left == 0:\n",
    "                    return ans\n",
    "                left -= 1\n",
    "                if nums[left] in hashtable.keys():\n",
    "                    hashtable[nums[left]] += 1\n",
    "                else:\n",
    "                    hashtable[nums[left]] = 1\n",
    "                numl = hashtable[nums[left]]\n",
    "                sum_k += choose(numl) - choose(numl - 1)\n",
    "            ans += left + 1\n",
    "            numr = hashtable[nums[right]]\n",
    "            sum_k -= choose(numr) - choose(numr - 1)\n",
    "            hashtable[nums[right]] -= 1\n",
    "            right -= 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        left = 0 \n",
    "        ans = 0\n",
    "        pairs = 0\n",
    "        for right,x in enumerate(nums):\n",
    "            cnt[x] +=1\n",
    "            pairs += (cnt[x] - 1)\n",
    "            \n",
    "            while  pairs - (cnt[nums[left]] - 1) >=k:\n",
    "                cnt[nums[left]] -=1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left +=1\n",
    "            if pairs >=k:\n",
    "                ans += left+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        cnt = collections.defaultdict(int)\n",
    "        pairs = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            pairs += cnt[num]\n",
    "            cnt[num] += 1\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                res += left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:  # 找到以x结尾的最短好数组\n",
    "                cnt[nums[left]] -= 1  # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1 # 最短 + 左端点小于left的所有子数组也是好数组\n",
    "            # print(ans, left, pairs, x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter()\n",
    "        m = 0\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for right, v in enumerate(nums):\n",
    "            if c[v]:\n",
    "                m += c[v]\n",
    "            c[v] += 1\n",
    "            \n",
    "            while m - (c[nums[left]]-1) >= k:\n",
    "                m -= c[nums[left]] - 1\n",
    "                c[nums[left]] -= 1\n",
    "                left += 1\n",
    "            #print(right, m, left)\n",
    "            if m >= k:\n",
    "                ans += left + 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        g = defaultdict(int)\n",
    "        ans = cur = 0\n",
    "        l, r, n = 0, 0, len(nums)\n",
    "        while r < n:\n",
    "            cur += g[nums[r]]\n",
    "            g[nums[r]] += 1\n",
    "            while cur >= k:\n",
    "                ans += (n - r)\n",
    "                cur -= (g[nums[l]] - 1)\n",
    "                g[nums[l]] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1 \n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1  # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        curs = 0\n",
    "\n",
    "        for x in nums:\n",
    "            # 当前x加进去以后，会贡献cnt[x]\n",
    "            curs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            # 看左端点是不是可以继续移动\n",
    "            # 如果去掉左端单，会减少 cnt[nums[l]] - 1的贡献\n",
    "            while curs - cnt[nums[l]] + 1 >= k:\n",
    "                cnt[nums[l]] -= 1\n",
    "                # 已经减掉 1了\n",
    "                curs -= cnt[nums[l]]\n",
    "                l += 1\n",
    "            # 出来的情况是满足要求的最大的l\n",
    "            if curs >= k:\n",
    "                ans += l + 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        window = {}\n",
    "        pairs = 0\n",
    "\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            # Add the new element to the window\n",
    "            if nums[right] not in window:\n",
    "                window[nums[right]] = 0\n",
    "            window[nums[right]] += 1\n",
    "\n",
    "            # Update the count of pairs\n",
    "            pairs += window[nums[right]] - 1\n",
    "\n",
    "            # If the current window has more than k pairs, remove the leftmost element\n",
    "            while pairs >= k:\n",
    "                window[nums[left]] -= 1\n",
    "                pairs -= window[nums[left]]\n",
    "                left += 1\n",
    "\n",
    "            # Update the count of good subarrays\n",
    "            count += left\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        cnt = Counter()\n",
    "        pairs = 0\n",
    "        for x in nums:  # nums[x] 是子数组最右边的数\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while pairs >= k:\n",
    "                # 移出左端点\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            # [0, left-1] 都可以作为子数组的左端点\n",
    "            ans += left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        slow = 0\n",
    "        n = len(nums)\n",
    "        hashmap = {}\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for fast in range(n):\n",
    "            if hashmap.get(nums[fast], -1) == -1:\n",
    "                hashmap[nums[fast]] = 1\n",
    "            else:\n",
    "                cnt += hashmap[nums[fast]]\n",
    "                hashmap[nums[fast]] += 1\n",
    "            while cnt>=k:\n",
    "                ans += (n-fast)\n",
    "                if hashmap[nums[slow]]>1:\n",
    "                    cnt -= (hashmap[nums[slow]]-1)\n",
    "                hashmap[nums[slow]] -= 1\n",
    "                slow += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        # c = Counter()\n",
    "        # n = len(nums)\n",
    "        # res = l = r = pairs = 0\n",
    "        # while r < n:\n",
    "        #     while r < n and pairs < k:\n",
    "        #         pairs += c[nums[r]]\n",
    "        #         c[nums[r]] += 1\n",
    "        #         r += 1 \n",
    "        #         res += l\n",
    "        #     while pairs >= k:\n",
    "        #         c[nums[l]] -= 1\n",
    "        #         pairs -= c[nums[l]]\n",
    "        #         l += 1\n",
    "        #         res += 1 \n",
    "        # return res \n",
    "\n",
    "        # ----------------------------------\n",
    "        cnt = Counter()\n",
    "        res = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                res += left + 1 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1  # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        mp = Counter()\n",
    "        cnt = ans = 0\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            cnt += mp[nums[right]]\n",
    "            mp[nums[right]]+=1\n",
    "            if cnt>=k:\n",
    "                ans+=1\n",
    "\n",
    "            while cnt - (mp[nums[left]]-1)>=k:\n",
    "                cnt -= mp[nums[left]]-1\n",
    "                mp[nums[left]]-=1\n",
    "                left+=1\n",
    "            ans += left\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        d = {}\n",
    "        count = 0\n",
    "        left = 0\n",
    "        for x in nums:\n",
    "            if x in d:\n",
    "                count += d[x]\n",
    "                d[x] += 1\n",
    "            else:\n",
    "                d[x] = 1\n",
    "            while count >= k:\n",
    "                d[nums[left]] -= 1\n",
    "                count -= d[nums[left]]\n",
    "                left += 1\n",
    "            res += left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        left=0\n",
    "        right=0\n",
    "        ddd={}\n",
    "        def Cm(m):\n",
    "            if m==0:\n",
    "                return 0\n",
    "            return m*(m-1)/2\n",
    "        result=0\n",
    "        nowsum=0\n",
    "\n",
    "        ddd[nums[0]]=1\n",
    "        while right<len(nums)-1:\n",
    "            right+=1\n",
    "            if nums[right] in ddd.keys():\n",
    "                ddd[nums[right]]=ddd[nums[right]]+1\n",
    "            else:\n",
    "                ddd[nums[right]]=1\n",
    "            #nowsum=nowsum+Cm(ddd[nums[right]])-Cm(ddd[nums[right]]-1)\n",
    "            nowsum=nowsum+ddd[nums[right]]-1\n",
    "            if nowsum>=k:\n",
    "                result+=len(nums)-right\n",
    "                while left<right:\n",
    "                    ddd[nums[left]]-=1\n",
    "                    #nowsum=nowsum-Cm(ddd[nums[left]]+1)+Cm(ddd[nums[left]])\n",
    "                    nowsum=nowsum-ddd[nums[left]]\n",
    "                    left+=1\n",
    "                    if nowsum>=k:\n",
    "                        result+=len(nums)-right\n",
    "                    else:\n",
    "                        break\n",
    "        while left<right: \n",
    "            ddd[nums[left]]-=1\n",
    "            nowsum=nowsum-ddd[nums[left]]\n",
    "            if nowsum>=k:\n",
    "                result+=1\n",
    "            else:\n",
    "                break\n",
    "            left+=1\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        cnt = collections.defaultdict(int)\n",
    "        pairs = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            pairs += cnt[num]\n",
    "            cnt[num] += 1\n",
    "            res += left # 只有满足条件之后left才会不为0\n",
    "            while pairs >= k:\n",
    "                res += 1\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1 # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1 # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        d = {}\n",
    "        count = 0\n",
    "        left = 0\n",
    "        for x in nums:\n",
    "            if x in d:\n",
    "                count += d[x]\n",
    "                d[x] += 1\n",
    "            else:\n",
    "                d[x] = 1\n",
    "            while count >= k:\n",
    "                d[nums[left]] -= 1\n",
    "                count -= d[nums[left]]\n",
    "                left += 1\n",
    "            res += left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        至少，双指针找范围\n",
    "        '''\n",
    "        left,right=0,-1\n",
    "        #双指针的初始值都有点不太敢确定，remake\n",
    "        #灵神说过要枚举右端点\n",
    "        #remake了，想得太久了,改成枚举左端点，找第一个符合条件的右端点\n",
    "        #remake了啊，真的想的太慢了\n",
    "        ans=0\n",
    "        cnt=Counter()\n",
    "        n=len(nums)\n",
    "        #remake,初始值确实是不会确定\n",
    "        s=0\n",
    "        while left<n:\n",
    "            #双指针的while居然还是不会，remake吧\n",
    "            while s<k and right<n-1:\n",
    "                right+=1\n",
    "                s+=cnt[nums[right]] #在right之前的cnt\n",
    "                cnt[nums[right]]+=1\n",
    "            if s>=k:\n",
    "                ans+=n-right\n",
    "            s-=cnt[nums[left]]-1\n",
    "            cnt[nums[left]]-=1\n",
    "            left+=1\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        ans=l=0\n",
    "        cnt=Counter()\n",
    "        n=len(nums)\n",
    "        t=0\n",
    "        for r,x in enumerate(nums):\n",
    "            t+=cnt[x]\n",
    "            cnt[x]+=1\n",
    "            while t>=k:\n",
    "                ans+=n-r\n",
    "                t-=cnt[nums[l]]-1\n",
    "                cnt[nums[l]]-=1\n",
    "                l+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        left=0\n",
    "        right=0\n",
    "        ddd={}\n",
    "        def Cm(m):\n",
    "            if m==0:\n",
    "                return 0\n",
    "            return m*(m-1)/2\n",
    "        result=0\n",
    "        nowsum=0\n",
    "\n",
    "        ddd[nums[0]]=1\n",
    "        while right<len(nums)-1:\n",
    "            right+=1\n",
    "            if nums[right] in ddd.keys():\n",
    "                ddd[nums[right]]=ddd[nums[right]]+1\n",
    "            else:\n",
    "                ddd[nums[right]]=1\n",
    "            nowsum=nowsum+Cm(ddd[nums[right]])-Cm(ddd[nums[right]]-1)\n",
    "            if nowsum>=k:\n",
    "                result+=len(nums)-right\n",
    "                while left<right:\n",
    "                    ddd[nums[left]]-=1\n",
    "                    nowsum=nowsum-Cm(ddd[nums[left]]+1)+Cm(ddd[nums[left]])\n",
    "                    left+=1\n",
    "                    if nowsum>=k:\n",
    "                        result+=len(nums)-right\n",
    "                    else:\n",
    "                        break\n",
    "        while left<right: \n",
    "            ddd[nums[left]]-=1\n",
    "            nowsum=nowsum-Cm(ddd[nums[left]]+1)+Cm(ddd[nums[left]])\n",
    "            if nowsum>=k:\n",
    "                result+=1\n",
    "            else:\n",
    "                break\n",
    "            left+=1\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            ans += left\n",
    "            while pairs >= k:\n",
    "                ans += 1\n",
    "                cnt[nums[left]] -= 1  # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1  # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1  # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        left, ans = 0, 0\n",
    "        cnt = defaultdict(int)\n",
    "        gs = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            gs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while gs >= k:\n",
    "                gs -= cnt[nums[left]] - 1\n",
    "                cnt[nums[left]] -= 1\n",
    "                left += 1\n",
    "            ans += left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            ans += left\n",
    "            while pairs >= k:\n",
    "                ans += 1\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        res = 0\n",
    "        left = 0\n",
    "        pairs = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            pairs += cnt[num]   # 先执行这行，原来没有出现过的字符即是0\n",
    "            cnt[num] += 1\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                res += left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        l = pairs = ans = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while pairs - (cnt[nums[l]] - 1) >= k:\n",
    "                cnt[nums[l]] -= 1\n",
    "                pairs -= cnt[nums[l]]\n",
    "                l += 1\n",
    "            if pairs >= k:\n",
    "                ans += l + 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        left = right = pairs = 0\n",
    "        n = len(nums)\n",
    "        hashTable = {}\n",
    "        cnt = 0\n",
    "        while right < n:\n",
    "            addE = nums[right]\n",
    "            right += 1\n",
    "            pairs += hashTable.get(addE, 0)\n",
    "            hashTable[addE] = hashTable.get(addE, 0) + 1\n",
    "            while pairs >= k:\n",
    "                cnt += n - right + 1\n",
    "                removeE = nums[left]\n",
    "                left += 1\n",
    "                pairs = pairs - hashTable.get(removeE) + 1\n",
    "                hashTable[removeE] -= 1 \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        left,right = 0,0\n",
    "        window = {}  # 统计数字出现的次数\n",
    "        pairs = 0\n",
    "        while right < n:\n",
    "            # 如果之前该数字出现过，则加入该数字后可多出window[nums[right]]对\n",
    "            # 例如出现过1词，那加入后变为2个，即多出1对\n",
    "            if nums[right] in window:\n",
    "                pairs += window[nums[right]]\n",
    "            window[nums[right]] = window.get(nums[right],0) + 1\n",
    "            while pairs >= k:\n",
    "                res += n - right\n",
    "                window[nums[left]] -= 1\n",
    "                pairs -= window[nums[left]]  # 注意这里pairs和window更新相对位置不一样，和第一个while不同\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        curs = 0\n",
    "        for x in nums:\n",
    "            curs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while curs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                curs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if curs >= k:\n",
    "                ans += left + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        # 1. 哈希表统计敞口内每个元素的出现次数\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1 # 移入右端点\n",
    "            while pairs - cnt[nums[left]] + 1 >= k:\n",
    "                cnt[nums[left]] -= 1 # 移出左端点\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        l,r = 0,0\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        mp = Counter()\n",
    "        while r < n:\n",
    "            cnt+=mp[nums[r]]\n",
    "            mp[nums[r]]+= 1\n",
    "            while cnt >= k:\n",
    "                ans += n-r\n",
    "                mp[nums[l]]-=1\n",
    "                cnt-=mp[nums[l]]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        left = right = num = ans = 0\n",
    "        n = len(nums)\n",
    "        while right < n:\n",
    "            m = nums[right]\n",
    "            num += d[m]\n",
    "            d[m] += 1\n",
    "            while num >= k:\n",
    "                ans = ans + n - right\n",
    "                x = nums[left]\n",
    "                left += 1\n",
    "                d[x] -= 1\n",
    "                num -= d[x]\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        pairs = left = ans = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            while pairs - (cnt[nums[left]] - 1) >= k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "            if pairs >= k:\n",
    "                ans += left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        至少，双指针找范围\n",
    "        '''\n",
    "        #其实就是双指针的一种变形，从满足条件->不满足条件\n",
    "        left=0\n",
    "        cnt=Counter()\n",
    "        s=0\n",
    "        ans=0\n",
    "        for right,x in enumerate(nums):\n",
    "            s+=cnt[x]\n",
    "            cnt[x]+=1\n",
    "            while s>=k:\n",
    "                s-=cnt[nums[left]]-1\n",
    "                cnt[nums[left]]-=1\n",
    "                left+=1\n",
    "            ans+=left\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        l,r = 0,0\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        mp = Counter()\n",
    "        while r < n:\n",
    "            mp[nums[r]]+= 1\n",
    "            if mp[nums[r]]>1:\n",
    "                cnt+=mp[nums[r]]-1\n",
    "            while cnt >= k:\n",
    "                ans += n-r\n",
    "                mp[nums[l]]-=1\n",
    "                cnt-=mp[nums[l]]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = left = pairs = 0\n",
    "        for x in nums:\n",
    "            pairs += cnt[x]\n",
    "            cnt[x] += 1\n",
    "            ans += left\n",
    "            while pairs >= k:\n",
    "                ans += 1\n",
    "                cnt[nums[left]] -= 1\n",
    "                pairs -= cnt[nums[left]]\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        至少，双指针找范围\n",
    "        '''\n",
    "        #其实就是双指针的一种变形，从满足条件->不满足条件\n",
    "        left=0\n",
    "        cnt=Counter()\n",
    "        s=0\n",
    "        ans=0\n",
    "        for right,x in enumerate(nums):\n",
    "            s+=cnt[x]\n",
    "            cnt[x]+=1\n",
    "            ans+=left\n",
    "            while s>=k:\n",
    "                s-=cnt[nums[left]]-1\n",
    "                cnt[nums[left]]-=1\n",
    "                left+=1\n",
    "                ans+=1\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter()\n",
    "\n",
    "        left = 0\n",
    "        cishu = 0\n",
    "        ans = 0\n",
    "        for i, nu in enumerate(nums):\n",
    "            cishu += c[nu]\n",
    "            c[nu] += 1\n",
    "            while cishu >= k:\n",
    "                c[nums[left]] -= 1\n",
    "                cishu -= c[nums[left]]\n",
    "                left += 1\n",
    "            ans += left\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter()\n",
    "        s = 0\n",
    "        for r, n in enumerate(nums):\n",
    "            c[n] += 1\n",
    "            v = c[n]\n",
    "            if v >= 2:\n",
    "                s += v-1\n",
    "            if s >= k: break\n",
    "        else:\n",
    "            return 0\n",
    "        def updateL(l, r):\n",
    "            nonlocal s\n",
    "            while l < r:\n",
    "                n = nums[l]\n",
    "                v = c[n]\n",
    "                if s - v + 1 < k: break\n",
    "                c[n] = v - 1\n",
    "                s -= v - 1\n",
    "                l += 1\n",
    "            return l\n",
    "        l = updateL(0, r)\n",
    "        res = l + 1\n",
    "        for r, n in enumerate(nums[r+1:], r+1):\n",
    "            c[n] += 1\n",
    "            v = c[n]\n",
    "            s += v -1\n",
    "            l = updateL(l, r)\n",
    "            res += l + 1\n",
    "        return res\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        mapping = {}\n",
    "        result = 0\n",
    "        left = 0\n",
    "        pairs = 0\n",
    "        for num in nums:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "            pairs += mapping[num] - 1\n",
    "            while(pairs >= k):\n",
    "                mapping[nums[left]] -= 1\n",
    "                pairs -= mapping[nums[left]]\n",
    "                if(mapping[nums[left]] == 0):\n",
    "                    del mapping[nums[left]]\n",
    "                left += 1\n",
    "            result += left\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        # 滑动窗口 + hash\n",
    "        lens = len(nums)\n",
    "        left, right = 0, 0\n",
    "        window = defaultdict(int)\n",
    "        res = 0\n",
    "        p = k\n",
    "        while right < lens:\n",
    "            cur = nums[right]\n",
    "            window[cur] += 1\n",
    "            if window[cur] > 1:\n",
    "                p -= window[cur] - 1\n",
    "            \n",
    "            while left < lens and p <= 0:\n",
    "                res += lens - right\n",
    "                temp = window[nums[left]] if nums[left] in window else 0\n",
    "                # 缩小一个单位左窗口\n",
    "                window[nums[left]] -= 1\n",
    "                if window[nums[left]] == 0:\n",
    "                    del window[nums[left]]\n",
    "                left += 1\n",
    "                \n",
    "                if temp > 1:\n",
    "                    p += temp - 1\n",
    "\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        nums_frequency_dict = {nums[0]:1}\n",
    "        nums_length = len(nums)\n",
    "        left, right = 0, 1\n",
    "        answer = 0\n",
    "        current_pair_sum = 0\n",
    "        while right < nums_length:\n",
    "            if nums[right] in nums_frequency_dict:\n",
    "                nums_frequency_dict[nums[right]] += 1\n",
    "                current_pair_sum += (nums_frequency_dict[nums[right]] - 1)\n",
    "            else:\n",
    "                nums_frequency_dict[nums[right]] = 1\n",
    "            while current_pair_sum >= k:\n",
    "                answer += nums_length - right\n",
    "                nums_frequency_dict[nums[left]] -= 1\n",
    "                if nums_frequency_dict[nums[left]]:\n",
    "                    current_pair_sum -= nums_frequency_dict[nums[left]]\n",
    "                else:\n",
    "                    del nums_frequency_dict[nums[left]]\n",
    "                left += 1\n",
    "            right += 1  \n",
    "        return answer\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        mapping = {}\n",
    "        result = 0\n",
    "        left = 0\n",
    "        pairs = 0\n",
    "        for num in nums:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                pairs += mapping[num]\n",
    "                mapping[num] += 1\n",
    "            while(pairs >= k):\n",
    "                mapping[nums[left]] -= 1\n",
    "                pairs -= mapping[nums[left]]\n",
    "                if(mapping[nums[left]] == 0):\n",
    "                    del mapping[nums[left]]\n",
    "                left += 1\n",
    "            result += left\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGood(self, nums: List[int], k: int) -> int:\n",
    "        # 滑动窗口 + hash\n",
    "        lens = len(nums)\n",
    "        left, right = 0, 0\n",
    "        window = defaultdict(int)\n",
    "        res = 0\n",
    "        p = k\n",
    "        while right < lens:\n",
    "            cur = nums[right]\n",
    "            window[cur] += 1\n",
    "            if window[cur] > 1:\n",
    "                p -= window[cur] - 1\n",
    "            \n",
    "            while p <= 0:\n",
    "                res += lens - right\n",
    "                temp = window[nums[left]] if nums[left] in window else 0\n",
    "                # 缩小一个单位左窗口\n",
    "                window[nums[left]] -= 1\n",
    "                if window[nums[left]] == 0:\n",
    "                    del window[nums[left]]\n",
    "                left += 1\n",
    "                \n",
    "                if temp > 1:\n",
    "                    p += temp - 1\n",
    "\n",
    "            right += 1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
